{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #String Transforms Into Another String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canConvert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串转化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出两个长度相同的字符串&nbsp;<code>str1</code>&nbsp;和 <code>str2</code>。请你帮忙判断字符串 <code>str1</code> 能不能在 <strong>零次</strong>&nbsp;或 <strong>多次</strong>&nbsp;<em>转化</em>&nbsp;后变成字符串 <code>str2</code>。</p>\n",
    "\n",
    "<p>每一次转化时，你可以将 <code>str1</code> 中出现的&nbsp;<strong>所有</strong>&nbsp;相同字母变成其他&nbsp;<strong>任何</strong>&nbsp;小写英文字母。</p>\n",
    "\n",
    "<p>只有在字符串 <code>str1</code>&nbsp;能够通过上述方式顺利转化为字符串 <code>str2</code>&nbsp;时才能返回 <code>true</code>&nbsp;。​​</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"aabcc\", str2 = \"ccdee\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>将 'c' 变成 'e'，然后把 'b' 变成 'd'，接着再把 'a' 变成 'c'。注意，转化的顺序也很重要。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>str1 = \"leetcode\", str2 = \"codeleet\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>我们没有办法能够把 str1 转化为 str2。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= str1.length == str2.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>str1</code>&nbsp;和 <code>str2</code> 中都只会出现小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [string-transforms-into-another-string](https://leetcode.cn/problems/string-transforms-into-another-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [string-transforms-into-another-string](https://leetcode.cn/problems/string-transforms-into-another-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabcc\"\\n\"ccdee\"', '\"leetcode\"\\n\"codeleet\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "        \n",
    "        convertion_map = dict()\n",
    "        unique_in_str2 = set()\n",
    "        \n",
    "        #确保一对一\n",
    "        for letter1, letter2 in zip(str1, str2):\n",
    "            if letter1 not in convertion_map:\n",
    "                convertion_map[letter1] = letter2\n",
    "                unique_in_str2.add(letter2)\n",
    "            elif convertion_map[letter1] != letter2:\n",
    "                 return False\n",
    "                \n",
    "        if len(unique_in_str2) < 26:\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "        \n",
    "        convertion_map = dict()\n",
    "        unique_in_str2 = set()\n",
    "        \n",
    "        #确保一对一\n",
    "        for letter1, letter2 in zip(str1, str2):\n",
    "            if letter1 not in convertion_map:\n",
    "                convertion_map[letter1] = letter2\n",
    "                unique_in_str2.add(letter2)\n",
    "            elif convertion_map[letter1] != letter2:\n",
    "                 return False\n",
    "          \n",
    "        print(convertion_map)\n",
    "        print(unique_in_str2)\n",
    "        if len(unique_in_str2) < 26:\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.roots = list(range(size))\n",
    "        self.ratings = [0]*size\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.roots[x] == x:\n",
    "            return x\n",
    "        self.roots[x] = self.find(self.roots[x])\n",
    "        return self.roots[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx, rooty = self.roots[x], self.roots[y]\n",
    "        if rootx != rooty:\n",
    "            if self.ratings[rootx] < self.ratings[rooty]:\n",
    "                self.roots[rooty] = rootx\n",
    "            elif self.ratings[rooty] < self.ratings[rootx]:\n",
    "                self.roots[rootx] = rooty\n",
    "            else:\n",
    "                self.roots[rooty] = rootx\n",
    "                self.ratings[rootx] += 1\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        # 26个英文字母占满的情况下，没有赋予的字符用作暂存字符\n",
    "        if len(Counter(str2)) == 26 and str1 != str2:\n",
    "            return False\n",
    "\n",
    "        n = len(str1)\n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        first = {}\n",
    "        for i, c in enumerate(str2):\n",
    "            if c not in first:\n",
    "                first[c] = i\n",
    "            else:\n",
    "                uf.union(first[c], i)\n",
    "        \n",
    "\n",
    "        first = {}\n",
    "        for i, c in enumerate(str1):\n",
    "            if c not in first:\n",
    "                first[c] = i\n",
    "            else:\n",
    "                if uf.find(first[c]) != uf.find(i):\n",
    "                    return False\n",
    "\n",
    "        return True        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "        n = len(str1)\n",
    "        post = dict()\n",
    "        for i in range(n):\n",
    "            a, b = str1[i], str2[i]\n",
    "            if a in post and post[a] != b:\n",
    "                return False\n",
    "            post[a] = b\n",
    "        return len(set(str2)) < 26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        has={}\n",
    "        cnt=Counter(str2)\n",
    "        if len(cnt)==26 and cnt.most_common(1)[0][1]==1 and str1!=str2:\n",
    "            return False\n",
    "        for s1,s2 in zip(str1,str2):\n",
    "            if s1 in has and has[s1]!=s2:\n",
    "              #  print(s1,has[s1],s2)\n",
    "                return False  \n",
    "            has[s1]=s2   \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        has={}\n",
    "        cnt1,cnt2=Counter(str1),Counter(str2)\n",
    "        if len(str1)==26 and all(cnt1[ch]==1 for ch in str1) and str1!=str2 \\\n",
    "        and len(str2)==26 and all(cnt2[ch]==1 for ch in str2):\n",
    "            return False\n",
    "        for s1,s2 in zip(str1,str2):\n",
    "            if s1 in has and has[s1]!=s2:\n",
    "                print(s1,has[s1],s2)\n",
    "                return False  \n",
    "            has[s1]=s2   \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        has={}\n",
    "        cnt1,cnt2=Counter(str1),Counter(str2)\n",
    "        if len(str1)==26 and all(cnt1[ch]==1 for ch in str1) and str1!=str2 \\\n",
    "        and len(str2)==26 and all(cnt2[ch]==1 for ch in str2):\n",
    "            return False\n",
    "        for s1,s2 in zip(str1,str2):\n",
    "            if s1 in has and has[s1]!=s2:\n",
    "              #  print(s1,has[s1],s2)\n",
    "                return False  \n",
    "            has[s1]=s2   \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        has={}\n",
    "        cnt1,cnt2=Counter(str1),Counter(str2)\n",
    "        if len(str1)==26 and all(cnt1[ch]==1 for ch in str1) and str1!=str2 \\\n",
    "        and len(str2)==26 and all(cnt2[ch]==1 for ch in str2):\n",
    "            return False\n",
    "        for s1,s2 in zip(str1,str2):\n",
    "            if s1 in has and has[s1]!=s2:\n",
    "              #  print(s1,has[s1],s2)\n",
    "                return False  \n",
    "            has[s1]=s2   \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        has={}\n",
    "        cnt=Counter(str2)\n",
    "        if len(str2)==26 and all(cnt[ch]==1 for ch in str2) and str1!=str2:\n",
    "            return False\n",
    "        for s1,s2 in zip(str1,str2):\n",
    "            if s1 in has and has[s1]!=s2:\n",
    "              #  print(s1,has[s1],s2)\n",
    "                return False  \n",
    "            has[s1]=s2   \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "        if len(set(str2)) == 26:\n",
    "            return False\n",
    "        d = [-1]*26\n",
    "        for i,(x,y) in enumerate(zip(str1,str2)):\n",
    "            idx = ord(x) - ord('a')\n",
    "            if d[idx] != -1 and str2[d[idx]] != str2[i]:\n",
    "                return False\n",
    "            d[idx] = i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.roots = list(range(size))\n",
    "        self.ratings = [0]*size\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.roots[x] == x:\n",
    "            return x\n",
    "        self.roots[x] = self.find(self.roots[x])\n",
    "        return self.roots[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx, rooty = self.roots[x], self.roots[y]\n",
    "        if rootx != rooty:\n",
    "            if self.ratings[rootx] < self.ratings[rooty]:\n",
    "                self.roots[rooty] = rootx\n",
    "            elif self.ratings[rooty] < self.ratings[rootx]:\n",
    "                self.roots[rootx] = rooty\n",
    "            else:\n",
    "                self.roots[rooty] = rootx\n",
    "                self.ratings[rootx] += 1\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if len(Counter(str2)) == 26 and str1 != str2:\n",
    "            return False\n",
    "\n",
    "        n = len(str1)\n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        first = {}\n",
    "        for i, c in enumerate(str2):\n",
    "            if c not in first:\n",
    "                first[c] = i\n",
    "            else:\n",
    "                uf.union(first[c], i)\n",
    "        \n",
    "\n",
    "        first = {}\n",
    "        for i, c in enumerate(str1):\n",
    "            if c not in first:\n",
    "                first[c] = i\n",
    "            else:\n",
    "                if uf.find(first[c]) != uf.find(i):\n",
    "                    return False\n",
    "\n",
    "        return True        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "        if len(set(str2)) == 26:\n",
    "            return False\n",
    "        d = {}\n",
    "        for i in range(len(str1)):\n",
    "            if str1[i] not in d:\n",
    "                d[str1[i]] = str2[i]\n",
    "            elif d[str1[i]] != str2[i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "      n = len(str1)\n",
    "      repeatedCharList = []\n",
    "      subtitudeMap = {}\n",
    "\n",
    "      for i in range(26):\n",
    "        char = chr(i+ord('a'))\n",
    "        subtitudeMap[char] = char\n",
    "      # charIndexsMap = collections.defaultdict(list)\n",
    "      for i in range(n):\n",
    "        if subtitudeMap[str1[i]] == str2[i]:\n",
    "          continue\n",
    "        else:\n",
    "          subtitudeMap[str1[i]] = str2[i]\n",
    "      \n",
    "      for i in range(n):\n",
    "        if subtitudeMap[str1[i]] != str2[i]: return False\n",
    "      \n",
    "      #checkLoop\n",
    "      checkList = [chr(x) for x in range(ord('a'), ord('z')+1)]\n",
    "      def findEndOfChain(startChar):\n",
    "        visited = set()\n",
    "        char = startChar\n",
    "        chainLen = 0\n",
    "        while char not in visited:\n",
    "          chainLen+=1\n",
    "          visited.add(char)\n",
    "          char = subtitudeMap[char]\n",
    "        return (chainLen, char)\n",
    "\n",
    "      DiffCharCount = len(set([subtitudeMap[x] for x in checkList]))\n",
    "      DiffCharCount = min(DiffCharCount, len(set(list(str1))))\n",
    "      print(DiffCharCount)\n",
    "\n",
    "      for char in checkList:\n",
    "        (chainLen, endChar) = findEndOfChain(char)\n",
    "        if chainLen >= 2 and endChar == char and DiffCharCount == 26:\n",
    "          print(subtitudeMap)\n",
    "          print(char, chainLen, endChar)\n",
    "          return False\n",
    "        \n",
    "      print(subtitudeMap)\n",
    "      return True\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def canConvert(self, str1: str, str2: str) -> bool:\n",
    "       if str1 == str2:\n",
    "           return True\n",
    "       \n",
    "       conversion_mappings = dict()\n",
    "       unique_characters_in_str2 = set()\n",
    "       \n",
    "       # 确保 str1 中的任何字符都没有映射到 str2 中的多个字符。\n",
    "       for letter1, letter2 in zip(str1, str2):\n",
    "           if letter1 not in conversion_mappings:\n",
    "               conversion_mappings[letter1] = letter2\n",
    "               unique_characters_in_str2.add(letter2)\n",
    "           elif conversion_mappings[letter1] != letter2:\n",
    "               # letter1 映射到 2 个不同的字符，因此 str1 无法转换为 str2。\n",
    "               return False\n",
    "       \n",
    "       \n",
    "       if len(unique_characters_in_str2) < 26:\n",
    "           # str1 中没有字符映射到 str2 中的两个或多个不同字符\n",
    "           # 并有至少一个可用于中断任何循环的临时字符。\n",
    "           return True\n",
    "       \n",
    "       # 转换映射形成一个或多个循环，并且没有可用于中断循环的临时字符，因此 str1 无法转换为 str2。\n",
    "       return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def canConvert(self, str1: str, str2: str) -> bool:\n",
    "       if str1 == str2:\n",
    "           return True\n",
    "       \n",
    "       conversion_mappings = dict()\n",
    "       unique_characters_in_str2 = set()\n",
    "       \n",
    "       # 确保 str1 中的任何字符都没有映射到 str2 中的多个字符。\n",
    "       for letter1, letter2 in zip(str1, str2):\n",
    "           if letter1 not in conversion_mappings:\n",
    "               conversion_mappings[letter1] = letter2\n",
    "               unique_characters_in_str2.add(letter2)\n",
    "           elif conversion_mappings[letter1] != letter2:\n",
    "               # letter1 映射到 2 个不同的字符，因此 str1 无法转换为 str2。\n",
    "               return False\n",
    "       \n",
    "       \n",
    "       if len(unique_characters_in_str2) < 26:\n",
    "           # str1 中没有字符映射到 str2 中的两个或多个不同字符\n",
    "           # 并有至少一个可用于中断任何循环的临时字符。\n",
    "           return True\n",
    "       \n",
    "       # 转换映射形成一个或多个循环，并且没有可用于中断循环的临时字符，因此 str1 无法转换为 str2。\n",
    "       return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "\n",
    "        mappings = dict()\n",
    "        unique_chars = set()\n",
    "\n",
    "        for letter1, letter2 in zip(str1, str2):\n",
    "            if letter1 not in mappings:\n",
    "                mappings[letter1] = letter2\n",
    "                unique_chars.add(letter2)\n",
    "            elif mappings[letter1] != letter2:\n",
    "                return False\n",
    "        \n",
    "        if len(unique_chars) < 26:\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvert(self, str1: str, str2: str) -> bool:\n",
    "        if str1 == str2:\n",
    "            return True\n",
    "        mapping = {}  # 保存从str1到str2的映射关系\n",
    "        for index in range(len(str1)):\n",
    "            if str1[index] not in mapping.keys():\n",
    "                mapping[str1[index]] = str2[index]\n",
    "            else:\n",
    "                if mapping[str1[index]] != str2[index]:\n",
    "                    return False\n",
    "        return len(set(mapping.values())) < 26\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
